/* 建立接口 list.h -- 简单链表类型的头文件 */

/* 使用 #ifndef 指令：防止多次包含一个头文件
 * C 标准头文件使用 #ifndef 技巧避免重复使用
 *
 * #ifndef 指令判断后面的标识符是否是未定义的，常用于定义之前未定义的常量
 *
 * #ifndef SIZE
        #define SIZE 100
   #endif
 *
 * #ifndef 指令可以防止相同的宏被重复定义
 * 在首次定义一个宏的头文件中用 #ifndef 指令激活定义，随后在其它头文件的定义都被忽略
 */
#ifndef List_h

#define List_h

#include <stdbool.h> //C99特性

#pragma mark - 数据表示
/*****************数据表示 *****************/

#define TSIZE 45 //存储电影名的数组大小
struct film
{
    char title[TSIZE];
    int rating;
};

//定义通用类型：方便以后重新定义 Item 类型，而无需修改 film 接口定义
typedef struct film Item;

/* 在链表的实现中，每一个链节叫做节点Node
 * 每个节点包含形成链表内容的信息和指向下一个节点的指针
 */
typedef struct node
{
    Item item;
    struct node * next;
} Node;

//将 List 作为 Node 类型的指针名：指向链表的开始处
typedef Node * List;


/* 上述程序定义了一个特定的结构作为 Item 类型
 * 然后根据 Item 类型定义了 Node，
 * 再根据 Node 定义了 List
 *
 */


#pragma mark - 函数原型

/***************** 函数原型 *****************/

/* 操   作：初始化一个链表
 * 前提条件（调用该函数前具备的条件）：plist指向一个链表
 * 后置条件（执行完该函数后的情况）：该链表初始化为空
 *
 * plist 一个指向指针的指针
 *
 * 讨论：使用 List 类型不必了解该类型变量的实现细节
 * 数据隐藏是一种从编程的更高层次隐藏数据表示细节的艺术。
 */
void InitializeList(List * plist);

/* 操作：确定链表是否为NULL，
 *      plist指向一个已初始化的链表
 * 返回值：如果链表为NULL，该函数返回 true；否则返回 false
 */
bool ListIsEmpty(const List *plist);

/* 操作：确定链表是否已满
 *      plist指向一个已初始化的链表
 * 返回值：如果链表为已满，该函数返回 true；否则返回 false
 *
 * 讨论：对链表而言，链表的大小取决于可用内存量
 * 该函数尝试为新项分配内存空间：如果分配失败，说明链表已满；如果分配成功，则必须释放刚才分配的内存供真正的项使用
 */
bool ListIsFull(const List *plist);

/* 操作：获取链表中的项数
 *      plist指向一个已初始化的链表
 * 返回值：返回链表中的项数
 *
 * 讨论：使用常用的链表算法遍历链表，同时统计链表中的项
 */
unsigned int ListItemCount(const List *plist);


/* 操作：在链表末尾添加项
 *      item 待添加至链表的项
 *      plist指向一个已初始化的链表
 * 返回值：如果添加成功，该函数返回 true；否则返回 false
 *
 * 讨论：该函数效率不是太高，它总是从链表的第 1 项l开始，然后搜索至链表末尾
 */
bool AddItem(Item item, List * plist);

/* 操作：遍历链表每一项
 *      plist指向一个已初始化的链表
 *      pfun 指向一个函数，该函数接受一个 Item 类型的参数，且无返回值
 * 后置条件：pfun 指向的函数作用于链表中的每一项一次
 */
void Traverse (const List *plist, void (* pfun)(Item item) );

/* 操作：释放已分配的内存
 *      plist指向一个已初始化的链表
 * 后置条件：释放为链表分配的所有内存，链表设置为空
 */
void EmptyTheList(List * plist);


#endif /* List_h */


/* 抽象数据类型 ADT
 *
 * 在编程时，应该根据编程问题匹配合适的数据类型：如使用 int 型表示多少部电影；使用 float 表示每部电影时长
 *
 * 什么是类型？类型特指两类信息：属性 和 操作
      如：int 类型的属性代表它是一个整数值；
         int 类型的操作有相加、相减、相乘、相除、求模。
 *
 * 要定义一个新的数据类型：首先，必须提供存储数据的方法，如设计一个结构。其次，必须提供操作数据的方法，如初始化、存储。
 *
 * 定义一种新类型，从抽象到具体经历 3 个步骤：
 * 1、提供类型属性和相关操作的抽象描述：这些描述既不能依赖特定的实现，也不能依赖特定的编程语言。这种正式的抽象描述被称为抽象数据类型 ADT
   2、开发一个实现 ADT 的编程接口：指明如何存储数据和执行所需操作的函数。如 提供结构定义和操作该结构的函数原型
   3、编写代码实现接口
 *
 *
 * 链表是一个能存储一系列项且可以对其进行所需操作的数据对象。
 * 链表具有哪些属性？首先，链表应该能存储一系列的项；其次，链表类型应该提供一些操作。一般的链表包含以下操作：
 * 初始化一个空链表；
 * 在链表末尾添加一个新项；
 * 确定链表是否为空；
 * 确定链表是否为已满；
 * 确定链表中的项数；
 * 访问链表中的每一项执行某些操作，如显示该项；
 * 在链表的任意位置插入一个项；
 * 移除链表中的一个项；
 * 在链表中检索一个项（不改变链表）；
 * 用另一个项替换链表中的一个项；
 * 在链表中搜索一个项
 *
 *
* 类 型 名：简单链表
* 类型属性：可以存储一系列项
* 类型操作：初始化链表为空
*           确定链表为空
*           确定链表已满
*           确定链表中的项数
*           在链表末尾添加项
*           遍历链表，处理链表中的项
*           清空链表
 *
 */
